﻿#include "二叉树.h"

#include <stdio.h>
#include <stdlib.h>

#include "队列.h"

二叉树节点_结构* 构造_二叉树节点(const int 数据)
{
    二叉树节点_结构 *节点 = malloc(sizeof(二叉树节点_结构));
    节点->数据 = 数据;
    节点->左孩子 = NULL;
    节点->右孩子 = NULL;
    return 节点;
}

void 销毁_二叉树节点(二叉树节点_结构* 节点)
{
    free(节点);
}

void 先序遍历整棵树(const 二叉树_引用结构 根, void (*执行函数)(二叉树节点_结构*))
{
    执行函数(根);
    if(根->左孩子 != NULL)
    {
        先序遍历整棵树(根->左孩子,执行函数);
    }
    if(根->右孩子 != NULL)
    {
        先序遍历整棵树(根->右孩子,执行函数);
    }
}

void 中序遍历整棵树(const 二叉树_引用结构 根, void (*执行函数)(二叉树节点_结构*))
{
    if(根->左孩子 != NULL)
    {
        中序遍历整棵树(根->左孩子,执行函数);
    }
    执行函数(根);
    if(根->右孩子 != NULL)
    {
        中序遍历整棵树(根->右孩子,执行函数);
    }
}

void 后序遍历整棵树(const 二叉树_引用结构 根,void (*执行函数)(二叉树节点_结构*))
{
    if(根->左孩子 != NULL)
    {
        后序遍历整棵树(根->左孩子,执行函数);
    }
    if(根->右孩子 != NULL)
    {
        后序遍历整棵树(根->右孩子,执行函数);
    }
    执行函数(根);
}

void 层次遍历整棵树(const 二叉树_引用结构 根, void (*执行函数)(二叉树节点_结构*))
{
    队列_结构 *队列 = 构造_队列(100);
    数据入队(队列, (unsigned long long)根);
    while (!队列空了(队列))
    {
        const 二叉树_引用结构 出队节点 = (二叉树_引用结构)数据出队(队列);
        if(出队节点->左孩子 != NULL)
        {
            数据入队(队列,(unsigned long long)出队节点->左孩子);
        }
        if(出队节点->右孩子 != NULL)
        {
            数据入队(队列,(unsigned long long)出队节点->右孩子);
        }
        执行函数(出队节点);
    }
    
    销毁_队列(队列);
}

void 销毁_整棵树(const 二叉树_引用结构 根)
{
    后序遍历整棵树(根,free);
}
